package com.expires.leecode;

import com.expires.leecode.bean.BinaryTreeNode;
import com.expires.leecode.bean.MultipleTreeNode;
import java.util.*;
/**
 * @program: SpringBootDemos
 * @description: 从根到叶的二进制数之和
 * @author: Kangsen
 * @create: 2022-05-30 10:13
 **/
/**
 * Definition for a binary tree node.
 * public class BinaryTreeNode {
 *     int val;
 *     BinaryTreeNode left;
 *     BinaryTreeNode right;
 *     BinaryTreeNode() {}
 *     BinaryTreeNode(int val) { this.val = val; }
 *     BinaryTreeNode(int val, BinaryTreeNode left, BinaryTreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Tree {
    public static int sumRootToLeaf(TreeNode root) {
        int total = 0;
        if(root == null){
            return 0;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            TreeNode popLeft = pop.left;
            TreeNode popRight = pop.right;
            if(popLeft !=null || popRight != null){
                if(popRight!=null){
                    int result = popRight.val + (pop.val << 1);
                    //修改right的值 但是这块修改好像是有问题 leecode会报错 因此这里创建对象入栈 对内存有影响
                    stack.push(new TreeNode(result,popRight.left,popRight.right));
                }
                if(popLeft != null){
                    int result = popLeft.val + (pop.val << 1);
                    stack.push(new TreeNode(result,popLeft.left,popLeft.right));
                }
            }else{
                //System.out.println("叶子节点  值"+ pop.val);
                total += pop.val;
            }
        }
        return total;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode treeNode = new TreeNode(0);
        treeNode.setLeft(new TreeNode(0));
        treeNode.setRight(new TreeNode(1));
        root.setLeft(treeNode);
        treeNode = new TreeNode(1);
        treeNode.setLeft(new TreeNode(0));
        treeNode.setRight(new TreeNode(1));
        root.setRight(treeNode);
        System.out.println(sumRootToLeaf(root));
    }
    public static class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         public TreeNode() {}
         public TreeNode(int val) { this.val = val; }
         public TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
         }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }

    /***
     * 二叉树的遍历：
     *      前序：根节点——>左子树 ——>右子树
     *      中序：左子树 -> 根节点 -> 右子树
     *      后序：左子树 -> 右子树 -> 根节点
     *      深度优先：根节点-> 左子树 一直到叶子节点  -> 右子树到叶子节点
     *      广度优先： 按层遍历  根节点-> 左节点 -> 右节点 ——> 左节点的左节点 -> 左节点的右节点 -> 右节点的左节点  -》 右节点的右节点。。。
     */
    static class BinaryTree{
        //二叉树创建的索引记录值
        private static int index = 0;
        //创建二叉树
        public static BinaryTreeNode createBinaryTree(int[] arr){
            BinaryTreeNode node = new BinaryTreeNode();
            if(arr.length == 0 || index > (arr.length -1)){
                return null;
            }else{
                int currentValue = arr[index];
                index += 1;
                if(currentValue == -1){
                    return null;
                }
                node.setValue(currentValue);
                node.setLeft(createBinaryTree(arr));
                node.setRight(createBinaryTree(arr));
            }
            return node;
        }
        //前序
        public static void traverse1(BinaryTreeNode BinaryTreeNode){
            //先遍历左子树 根 再遍历右子树
            if(BinaryTreeNode == null){
                return;
            }
            System.out.print(BinaryTreeNode.getValue()+"  ");
            traverse1(BinaryTreeNode.getLeft());
            traverse1(BinaryTreeNode.getRight());
        }

        //中序  左根右
        public static void traverse2(BinaryTreeNode BinaryTreeNode){
            if(BinaryTreeNode == null){
                return;
            }
            traverse2(BinaryTreeNode.getLeft());
            System.out.print(BinaryTreeNode.getValue()+"  ");
            traverse2(BinaryTreeNode.getRight());
        }

        //后序  左右根
        public static void traverse3(BinaryTreeNode BinaryTreeNode){
            if(BinaryTreeNode == null){
                return;
            }
            traverse3(BinaryTreeNode.getLeft());
            traverse3(BinaryTreeNode.getRight());
            System.out.print(BinaryTreeNode.getValue()+"  ");
        }

        //广度优先 按层遍历 链表实现
        public static void traverse4(BinaryTreeNode BinaryTreeNode){
            if(BinaryTreeNode == null){
                return;
            }
            LinkedList<BinaryTreeNode> linkedList = new LinkedList<>();
            linkedList.add(BinaryTreeNode);
            while(!linkedList.isEmpty()){
                BinaryTreeNode node = linkedList.poll();
                System.out.print(node.getValue() + "  ");
                if(node.getLeft() != null){
                    linkedList.add(node.getLeft());
                }
                if(node.getRight() != null){
                    linkedList.add(node.getRight());
                }
            }
        }

        //深度优先  根——左子树——左叶子——右子树——有叶子  栈
        public static void traverse5(BinaryTreeNode BinaryTreeNode){
            if(BinaryTreeNode == null){
                return;
            }
            Stack<BinaryTreeNode> stack = new Stack<>();
            stack.add(BinaryTreeNode);
            while(!stack.isEmpty()){
                BinaryTreeNode node = stack.pop();
                System.out.print(node.getValue()+"  ");
                if(node.getRight()!=null){//这里必须是右边先进待在栈底
                    stack.push(node.getRight());
                }
                if(node.getLeft()!=null){
                    stack.push(node.getLeft());
                }
            }
        }

        public static void main(String[] args) {
            BinaryTreeNode node = createBinaryTree(new int[]{1, 2, -1,4, -1,-1, 3, 5, -1,-1,6, -1,-1});
            System.out.println("前序:");
            traverse1(node);
            System.out.println();

            System.out.println("中序:");
            traverse2(node);
            System.out.println();

            System.out.println("后序:");
            traverse3(node);
            System.out.println();

            System.out.println("广度优先BFS:");
            traverse4(node);
            System.out.println();

            System.out.println("深度优先DFS:");
            traverse5(node);
            System.out.println();
        }
    }

    /**
     * 树的遍历：
     *  深度优先DFS：
     *  广度优先BFS：
     */
    static class MultipleNodeTree{
        private static int index = 0;
        public static MultipleTreeNode createBinaryTree(Map<String,String[]> map){
            /*if(map.isEmpty()){
                return new MultipleTreeNode();
            }
            MultipleTreeNode multipleTreeNode = new MultipleTreeNode();
            Iterator<Map.Entry<String, String[]>> iterator = map.entrySet().iterator();
            while (iterator.hasNext()){
                new MultipleTreeNode();
                Map.Entry<String,String[]> nex = iterator.next();
                String value = multipleTreeNode.getValue();
                if(value != null && !value.equalsIgnoreCase("")){
                    value = nex.getKey();
                }
                multipleTreeNode.setValue(value);

            }*/
            //a的子节点
            MultipleTreeNode multipleTreeNode = new MultipleTreeNode();
            List<MultipleTreeNode> list = new ArrayList<>();

            MultipleTreeNode multipleTreeNode_e = new MultipleTreeNode();
            multipleTreeNode_e.setValue("e");
            list = new ArrayList<>();
            list.add(new MultipleTreeNode("l",null));
            list.add(new MultipleTreeNode("m",null));
            list.add(new MultipleTreeNode("n",null));
            multipleTreeNode_e.setchildNodes(list);

            MultipleTreeNode multipleTreeNode_b = new MultipleTreeNode();
            multipleTreeNode_b.setValue("b");
            list = new ArrayList<>();
            list.add(multipleTreeNode_e);
            list.add(new MultipleTreeNode("f",null));
            list.add(new MultipleTreeNode("g",null));
            multipleTreeNode_b.setchildNodes(list);

            MultipleTreeNode multipleTreeNode_h = new MultipleTreeNode();
            multipleTreeNode_h.setValue("h");
            list = new ArrayList<>();
            list.add(new MultipleTreeNode("o",null));
            list.add(new MultipleTreeNode("p",null));
            multipleTreeNode_h.setchildNodes(list);

            MultipleTreeNode multipleTreeNode_c = new MultipleTreeNode();
            multipleTreeNode_c.setValue("c");
            list = new ArrayList<>();
            list.add(multipleTreeNode_h);
            list.add(new MultipleTreeNode("i",null));
            multipleTreeNode_c.setchildNodes(list);

            MultipleTreeNode multipleTreeNode_d = new MultipleTreeNode();
            multipleTreeNode_d.setValue("d");
            list = new ArrayList<>();
            list.add(new MultipleTreeNode("j",null));
            list.add(new MultipleTreeNode("k",null));
            multipleTreeNode_d.setchildNodes(list);


            multipleTreeNode.setValue("a");
            list = new ArrayList<>();
            list.add(multipleTreeNode_b);
            list.add(multipleTreeNode_c);
            list.add(multipleTreeNode_d);
            multipleTreeNode.setchildNodes(list);

            return multipleTreeNode;
        }

        //广度遍历
        public static void traverseBFS(MultipleTreeNode multipleTreeNode){
            if(multipleTreeNode == null){
                return;
            }
            LinkedList<MultipleTreeNode> linkedList = new LinkedList<>();
            linkedList.add(multipleTreeNode);
            while (!linkedList.isEmpty()){
                MultipleTreeNode node = linkedList.poll();
                System.out.print(node.getValue() + " ");
                if(node.getchildNodes()!=null && !node.getchildNodes().isEmpty()){
                    for (MultipleTreeNode treeNode : node.getchildNodes()) {
                        linkedList.add(treeNode);
                    }
                }
            }
        }

        //深度遍历DFS
        public static void traverseDFS(MultipleTreeNode multipleTreeNode){
            if(multipleTreeNode == null){
                return;
            }
            Stack<MultipleTreeNode> stack = new Stack<>();
            stack.push(multipleTreeNode);
            while (!stack.isEmpty()){
                MultipleTreeNode node = stack.pop();
                System.out.print(node.getValue() + " ");
                //这里可以倒序进栈 list倒序遍历
                if(node.getchildNodes()!=null && !node.getchildNodes().isEmpty()){
                    for (int i = node.getchildNodes().size() - 1; i >= 0; i--) {
                        stack.push(node.getchildNodes().get(i));
                    }
                }
            }
        }
        public static void main(String[] args) {
            MultipleTreeNode multipleTreeNode = createBinaryTree(null);
            System.out.println("广度优先 按层：");
            traverseBFS(multipleTreeNode);
            System.out.println();
            System.out.println("深度优先：");
            traverseDFS(multipleTreeNode);
        }
    }
}
